package com.leetcode.partition22;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/3/4 21:13
 */
public class LC2104子数组范围和_线段树 {

    private static final int N = 1010, INF = 0x3f3f3f3f;
    private static int[] nums = new int[N];
    private static Node[] tr = new Node[N << 2];
    private static int n = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        int[] nums = new int[n];
        String[] ss = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(ss[i]);
        writer.write(subArrayRanges(nums) + "\n");
        writer.flush();
    }

    public static long subArrayRanges(int[] _nums) {
        n = _nums.length;
        System.arraycopy(_nums, 0, nums, 1, n);
        long ans = 0;
        build(1, 1, n);
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                //查找[i,j]的最大值和最小值
                ans += queryMaxv(1, i, j) - queryMinv(1, i, j);
            }
        }
        return ans;
    }

    private static void build(int u, int l, int r) {
        if (l == r) tr[u] = new Node(l, r, nums[l], nums[l]);
        else {
            int mid = l + r >> 1;
            tr[u] = new Node(l, r);
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }

    private static int queryMaxv(int u, int l, int r) {
        if (l <= tr[u].l && r >= tr[u].r) return tr[u].maxv;
        int mid = tr[u].l + tr[u].r >> 1, res = -INF;
        if (l <= mid) res = queryMaxv(u << 1, l, r);
        if (r > mid) res = Math.max(res, queryMaxv(u << 1 | 1, l, r));
        return res;
    }

    private static int queryMinv(int u, int l, int r) {
        if (l <= tr[u].l && r >= tr[u].r) return tr[u].minv;
        int mid = tr[u].l + tr[u].r >> 1, res = INF;
        if (l <= mid) res = queryMinv(u << 1, l, r);
        if (r > mid) res = Math.min(res, queryMinv(u << 1 | 1, l, r));
        return res;
    }

    private static void pushup(int u) {
        tr[u].maxv = Math.max(tr[u].maxv, Math.max(tr[u << 1].maxv, tr[u << 1 | 1].maxv));
        tr[u].minv = Math.min(tr[u].minv, Math.min(tr[u << 1].minv, tr[u << 1 | 1].minv));
    }

    private static class Node {
        private int l, r;
        private int maxv, minv;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
            maxv = -INF;
            minv = INF;
        }

        public Node(int l, int r, int maxv, int minv) {
            this.l = l;
            this.r = r;
            this.maxv = maxv;
            this.minv = minv;
        }
    }
}
